# 09. 跳跃游戏.py
from typing import List
# 如果非负整数数组中没有0的话，则肯定可以跳到最后一个位置。
# 如果非负整数组中有零的话，只需要遇到0之前的某一个位置存在跳过这里的可能的话，那就也可以达到最后一个位置。
# 所以进行单次遍历，然后时刻统计已经遍历的元素中 nums[i]+i 的最大值，在遇到0值的时候进行对比即可。
# 需要考虑一种情况（刚好能抵达最后一个元素，但是最后一个元素为0）的两个特例：
# 1. 只有一个元素，且改元素为0，则视为True，因为最初就位于第一个下标
# 2. 有多个元素，最后一个一个元素为0，但是0可以抵达。
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        max_jump_index = 0
        ans = True
        # 特判：[ 0 ]
        if nums[0] == 0 and length == 1:
            return True
        for i in range(length):
            max_jump_index = max(max_jump_index, nums[i]+i)
            # 如果存在不在最后一位的零的话，那么需要跨过这个0才能到达终点
            if nums[i] == 0:
                if max_jump_index <= i != length-1:
                    ans = False
                    break
        return ans


class Standard_Solution:
    # 贪心思维：维护最远可达的位置；判断最远可达位置是否包含最后一个位置
    # 判断所有可达情况，其余情况一律返回不可达。
    def canJump(self, nums: List[int]) -> bool:
        n, rightmost = len(nums), 0
        for i in range(n):
            if i <= rightmost:
                rightmost = max(rightmost, i + nums[i])
                if rightmost >= n - 1:
                    return True
        return False